package baseclass.m_graph;

import java.util.*;

/**
 *      Kruskal算法是基于贪心的思想得到的。
 *      首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，
 *      如果这条边的两个端点不属于同一集合，那么就将它们合并，
 *      直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，
 *      那么这里我们就可以用到一个工具——-并查集。
 *      换而言之，Kruskal算法就是基于并查集的贪心算法。
 * 算法流程：
 * 	(1)将图G看做一个森林，每个顶点为一棵独立的树【每个点加入各自的并查集】
 * 	(2)将所有的边加入集合S，即一开始S = E
 * 	(3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树【把这两个点加入并查集】，同时将(u,v)加入生成树的边集E'【记录对应的边】
 * (4)重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树
 * @date 2020/3/6 21:43
 */
public class Code04_Kruskal {
    /**
     * unionFindSet.isSameSet和unionFindSet.union时间复杂度都是o(1),
     * ！edgeQ.isEmpty以及初始化放入边时间复杂度都是O(e),所以时间复杂度是O(e)，e为边数
     */
    public static Set<Edge> kruskalMST(Graph graph){
        if(graph == null) return new HashSet<>();
        Queue<Edge> edgeQ = new PriorityQueue<>((e1,e2)-> e1.weight - e2.weight);
        for (Edge edge : graph.edges) {
            edgeQ.offer(edge);
        }
        Set<Edge> res = new HashSet<>();
        UnionFindSet sameSet =
                new UnionFindSet(new LinkedList<>(graph.nodes.values()));
        while (!edgeQ.isEmpty()){
            Edge edge = edgeQ.poll();
            if(!sameSet.isSameSet(edge.from,edge.to)){
                res.add(edge);
                sameSet.union(edge.from,edge.to);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Integer[][]matrix = {{1,1,2},{2,1,3},{2,1,4},{1,2,3},{3,2,4},{4,3,4}};
        Graph graph = Graph.createGraph(matrix);
        Set<Edge> edges = kruskalMST(graph);
        for (Edge edge : edges) {
            System.out.println(edge.from.val+"->"+edge.to.val+" 权重:"+edge.weight);
        }
    }
}
